//翻转对
//https://leetcode.cn/problems/reverse-pairs/
public class Test {
    public static void main(String[] args) {
        //
    }
}

class Solution {
    int ret;
    //int[] index;
    int[] tmpNums;
    //int[] tmpIndex;

    public int reversePairs(int[] nums) {
        //
        int n = nums.length;
        //index = new int[n];
        tmpNums = new int[n];
        //tmpIndex = new int[n];

        //for (int i = 0; i < n; i++) {
        //    index[i] = i;
        //}
        func(nums,0,n-1);
        return ret;
    }

    private void func(int[] nums, int l, int r) {
        if(l>=r) return;
        //int mid = (l+r)/2;
        int mid = l + (r-l)/2;//防止溢出
        func(nums,l,mid);
        func(nums,mid+1,r);

        //一左一右的情况（降序）
        //先count，再排序
        int cur1 = l, cur2 = mid+1;
        while(cur1<=mid&&cur2<=r){
            if(nums[cur1]<=2*nums[cur2]){
                //
                cur2++;
            }else{
                //
                ret+=(r-cur2+1);
                cur1++;
            }
        }
        //排序
        cur1 = l;
        cur2 = mid+1;
        int i = l;
        while(cur1<=mid&&cur2<=r){
            if(nums[cur1]>=nums[cur2]){
                tmpNums[i] = nums[cur1++];
            }else{
                tmpNums[i] = nums[cur2++];
            }
            i++;
        }
        while(cur1<mid){
            tmpNums[i++] = nums[cur1++];
        }
        while(cur2<r){
            tmpNums[i++] = nums[cur2++];
        }
        for(int j = l;j<=r;j++){
            nums[j] = tmpNums[j];
        }
    }
}
